The amount of data transmitted over telecommunications networks increases rapidly. High speed and high capacity packet data networks and servers are employed for transferring these data. Amongst others for test and monitoring purposes, to guarantee a desired or agreed Quality of Service, QoS, for example, packet header information on, for example, source and destination addresses is not sufficient to obtain the required information. In some cases the payload of data packets needs to be inspected for particular data patterns, for example. Data mining, detection of data viruses and other malicious data are further examples that may require packet data inspection.
A method of inspecting packets is by employing finite automata. A finite automata, or simply a state machine, is a computer controlled method that is employed as an abstract state machine operating on states according to a state transition table or state transition register. Such state transition table comprises—for a plurality of states of the finite automata—a transition from a present to a next state upon inputting a particular data symbol in the present state, eventually leading to a data pattern match of a particular string of input data symbols. Such data symbols are, for example, the data symbols comprised in the well-known American Standard Code for Information Interchange, or in short the ASCII table. As such, a state transition to a subsequent state may also involve a transition to the same state of the automata, called a non-forwarding transition. Processing finite automata may involve relatively high memory storage and memory access, dependent on the complexity of the automata, i.e. the number of states, state transitions and the dimensions of the state transition table.
In general, two types of finite automata can be distinguished. Deterministic Finite Automata, DFA, and Non-deterministic Finite Automata, NFA. DFA is preferred at processing speed, as it requires only constant amount of memory accesses while parsing thru the packet payload. The cost of such computation efficiency is the high memory storage. NFA has lower memory storage requirements but as from every state the next state can be several other in parallel, it requires a lot of computation resources to check every possible case.
Both DFA and NFA have their own strengths and weaknesses and can be employed in software tools for data packet inspection systems.
Network servers performing the finite automata comprise a certain amount of memory which can be classified in a plurality of memory levels. These have their own characteristics in terms of throughput and latency. In most parallel systems at least L1 and L2 type memory are present. L1 is most often dedicated to a single core of the multicore execution unit, and L2 is most often shared over a plurality of cores. As such however, the number of parallel read/write instructions are limited by the number of memory controllers.
Even within the same level of memory such differences can be present, as sometimes different types of memory are combined in single server. In case of real-time packet processing several packets are processed at the same time, usually by utilizing multicore execution units or other parallel hardware. Care should be taken to not completely occupy al of the memory resources with executing the finite automata. Especially as most finite automata are executed in a network server also serving other network and communication tasks.
As the amount of data transmitted over telecommunications networks increases rapidly, software employing conventional DFA of FNA may require a too high amount of resources, i.e. memory storage and memory access controllers, generally designated as memory footprint. Accordingly, there is a need for improved methods of detecting data patterns executing finite automata.